// 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

// 添加备注

// 执行用时：
// 4 ms
// , 在所有 C++ 提交中击败了
// 36.95%
// 的用户
// 内存消耗：
// 7.3 MB
// , 在所有 C++ 提交中击败了
// 5.04%
// 的用户

#include<vector>
#include<string>
#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> res;
    vector<string> letterCombinations(string digits) {
        if(size(digits) == 0){
            return res;
        }
        string res_temp = "";
        dfs(digits,res_temp);
        return res;
    }

    void dfs(string s,string res_temp){
        string s_temp ="";
        if(size(s)>0){
            for(int i = 1; i < size(s) ; i++){
                s_temp = s_temp + s[i];
            }
            if(s[0] == '2'){
                dfs(s_temp,res_temp + 'a');
                dfs(s_temp,res_temp + 'b');
                dfs(s_temp,res_temp + 'c');
            }
            else if(s[0] == '3'){
                dfs(s_temp,res_temp + 'd');
                dfs(s_temp,res_temp + 'e');
                dfs(s_temp,res_temp + 'f');
            }
            else if(s[0] == '4'){
                dfs(s_temp,res_temp + 'g');
                dfs(s_temp,res_temp + 'h');
                dfs(s_temp,res_temp + 'i');
            }
            else if(s[0] == '5'){
                dfs(s_temp,res_temp + 'j');
                dfs(s_temp,res_temp + 'k');
                dfs(s_temp,res_temp + 'l');
            }
            else if(s[0] == '6'){
                dfs(s_temp,res_temp + 'm');
                dfs(s_temp,res_temp + 'n');
                dfs(s_temp,res_temp + 'o');
            }
            else if(s[0] == '7'){
                dfs(s_temp,res_temp + 'p');
                dfs(s_temp,res_temp + 'q');
                dfs(s_temp,res_temp + 'r');
                dfs(s_temp,res_temp + 's');
            }
            else if(s[0] == '8'){
                dfs(s_temp,res_temp + 't');
                dfs(s_temp,res_temp + 'u');
                dfs(s_temp,res_temp + 'v');
            }
            else if(s[0] == '9'){
                dfs(s_temp,res_temp + 'w');
                dfs(s_temp,res_temp + 'x');
                dfs(s_temp,res_temp + 'y');
                dfs(s_temp,res_temp + 'z');
            }
        }
        else{
            res.push_back(res_temp);
            return;
        }
    }
};